Since the advent of the electronic computer in reliable form, workers in the art have given much consideration to systems employing a number of computers functioning together in interrelated fashion to accomplish a given overall task. In some of these multiprocessor systems a large computer utilizes its superior speed and capacity to perform the complex portions of a program, but assigns smaller and slower satellite processors the less complicated and less urgent tasks in order to reduce the load and demands upon the large computer. The large computer is required to undertake the responsibilities of assigning subtasks, making sure that the smaller processors are kept occupied, ascertaining the availability and performance of the smaller processors, and providing a unified result.
Other multiprocessor systems utilize a different approach, employing a plurality of processors and a common bus system, with the processors having essential equality of function. In this type of system, separate control computers or control systems are often used to monitor the availability and capability of an individual processor for a given subtask, and to control the routing of tasks and information between processors. The processors may be arranged and operated so that they monitor the status and availability of the other processors and determine the routing of messages and programs. The common and substantial drawback of these systems is that the software and operating time required for overhead and maintenance functions interfere with the performance of the principal objectives. Problems of routing and monitoring may increase dramatically in relation to the number of processors involved, so that ultimately a disproportionate amount of effort is spent in overhead functions.
Since the days of the early "Binac" (two parallel processors) and comparable systems it has been recognized that a multiprocessor provides a redundant capability that can substantially improve the overall reliability of an operating system. Actual installations of multiprocessor systems have until recently been quite limited, largely due to the extensive software problems involved. Nevertheless, the advantages of multiprocessor operation for real time applications and other situations in which system down time cannot be tolerated have led to the development of systems which are successful in operation but which nevertheless involve significant commitments to overhead software and operating time.
Illustrative of multitasking systems are U.S. Pat. Nos. 3,445,822, 3,566,363 and 3,593,300, all relating to a system in which multiple computers access a single shared main memory, and in which capabilities and requirements are compared in order to assign tasks optimally to individual processors.
Another example of the prior art is U.S. Pat. No. 4,099,233, in which a number of processors share a single bus and a control unit incorporating a buffer register is used in the transfer of data blocks between a transmitting miniprocessor and a receiving miniprocessor. This concept has been employed in a distributed mail sorting system in Europe.
U.S. Pat. No. 4,228,496 pertains to a multiprocessor system in which buses between processors are coupled to bus controllers which monitor transmissions and determine the priority of data transfers between processors, each of which can be coupled in to control a certain part of a number of peripheral devices.
The "Ethernet" system, described in U.S. Pat. No. 4,063,220 and U.S. Pat. No. 4,099,024 discloses another approach to the problem of intercommunicating between different processors and peripherals. All units are coupled to a common multiple access network and compete for priority. Collision detection is based upon time priority, which in turn means that global capabilities cannot readily be controlled, coordinated or given specificity.
Details of these complex systems can only be fully appreciated by analysis of the patents and any related publications. However, review will verify that in each instance prioritizing of data transfer and the selection of processors requires extensive intercommunication and supervisory control if tasks are to be shared. Expansion of the systems to include additional processors does not present identical problems with these different systems, but in each instance substantially complicates system software, applications programming, hardware, or all three.
In most networks, each message is positively acknowledged when it reaches the destination node by sending an acknowledgement word back along the path used to transmit the message (this technique applies to both circuit switched and packet switched networks). Thus, a source node enqueues its message into the network and starts a countdown timer. If the positive acknowledgement is received before the timer expires, the message transmission is considered successful. If the timer expires before an acknowledgement is received, the message transmission is considered a failure and the message must be resent.
The problem with the above scheme is that the source node only knows if the message succeeds or fails, no maximum progress report is given. Message failure might have been caused by several reasons including network congestion, broken links, transmission errors, and node errors. Since the source node does not know the cause of the failure or the maximum message progress, its only option is to retry sending the message or abort the message.
An obvious improvement to the above scheme is to add negative acknowledgements that indicate why the message failed. Thus, some single-dimensional (one path) networks return specific status words when the message transfer has failed. However, this method does not scale to multidimensional networks where multiple paths can fail. In the above example, suppose Node 1's children, Nodes 2 and 4, both fail sending the message for different reasons. They both return this information to Node 1. Node 1 must then return both errors to Node 0, requiring Node 0 to process every error that occurs on every search path. While this protocol satisfies the expendability need, it requires too much overhead memory by not encapsulating status information into a single status word. Furthermore, too much network bandwidth is required to support this method.
A final refinement to the scheme would allow intermediate nodes to accumulate error reports and pass only the most severe error report to its parent. Although this scheme reduces the acknowledgement message traffic, it does not encapsulate the message progress through the network. Using this scheme, the source node is only informed of the most severe error occurring on any search branch without any information regarding message progress being reported.
Inherent constraints on multiprocessor system size and capability are imposed by the use of one or two logically passive busses. While different techniques can be employed to facilitate intercommunication, such as the grouping of subsystems into global resources evidenced in U.S. Pat. No. 4,240,143, the amount of useful traffic must reach a limit and variable delays impose insuperable problems when large numbers of processors are used. Situations may arise in which one or more processors become locked out or deadlocked, and these circumstances in turn require added circuitry and software to resolve the problems. The impracticality of substantially extending the number of processors, say to 1024, thus becomes evident.
It is desirable for many applications to depart from the constraints of these existing approaches and to utilize modern technology to best advantage. The lowest cost technology available today is based upon mass produced microprocessors, and high capacity rotating disk memories, such as Winchester technology devices using small head to disk spacing in a sealed environment.
It is desirable to expand a multiprocessor system without disproportionate or even concomitant software complexity. It is desirable further to be able to handle computer problems that may be characterized as having a distributed structure, in which an overall function can be dynamically subdivided into limited or iterative processing tasks.
Virtually all data base machines fall into this category, which also includes such other typical examples as sorting, pattern recognition and correlation, digital filtering, large matrix computations, simulation of physical systems and the like. In all of these situations there is a requirement for widely dispersed, relatively straight-forward individual processing tasks with a high instantaneous task load. This situation unduly burdens prior art multiprocessor systems because it tends to increase the time and software involved in overhead, and because practical difficulties arise in implementation of the systems. Using a shared passive bus, for example, propagation rates and data transfer times introduce an absolute barrier as to the rate at which transactions can be processed.